﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 6031)
#include "heap.h"

//堆
void test1()
{
	hp hp;
	hpinit(&hp);
	int arr[] = { 10,50,40,23,51,20 };
	int size = sizeof(arr) / sizeof(*arr);
	int i = 0;
	for (i = 0; i < size; i++)
	{
		hppush(&hp, arr[i]);
	}

	while (!hpempty(&hp))
	{
		printf("%d\n", hptop(&hp));
		hppop(&hp);
	}

	hpdestroy(&hp);
}

//堆排序
void jump(int* arr, int sz) //向上调整建堆
{
	int i = 0;
	for (i = 1; i < sz; i++)
	{
		hpjump(arr, i);
	}

	int end = sz - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		hpdown(arr, end, 0);
		end--;
	}
}

void down(int* arr, int sz)		//向下调整建堆
{
	int i = 0;
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		hpdown(arr, sz, i);
	}

	int end = sz - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		hpdown(arr, end, 0);
		end--;
	}
}

void test2()
{
	int arr[] = { 8,6,7,0,1,3,2,4,5 };
	int sz = sizeof(arr) / sizeof(*arr);
	down(arr, sz);
}

void topk(int* arr, int sz, int k)
{
	int* p = (int*)malloc(sizeof(int) * k);
	if (!p)
	{
		perror("malloc");
		return;
	}

	int i = 0;
	for (i = 0; i < k; i++)
	{
		p[i] = arr[i];
	}

	for (i = 1; i < k; i++)
	{
		hpjump(p, i);
	}

	for (i = k + 1; i < sz; i++)
	{
		if (p[0] < arr[i])
		{
			p[0] = arr[i];
			hpdown(p, k, 0);
		}
	}

	for (i = 0; i < k; i++)
	{
		printf("%d ", p[i]);
	}
}

void test3()
{
	int arr[] = { 100,50,7,0,1,3,2,4,5 };
	int sz = sizeof(arr) / sizeof(*arr);
	topk(arr, sz, 3);
}


int main()
{
	test3();
	return 0;
}